//
// Created by ZYZ on 2020/6/9.
//

#include <cstdio>
#include <iostream>
#include "../../include/type_list.h"
#include "static_linked_list.h"

void InitSpace_SL(SLinkList &space) {
    //将一维数组 space 中各分量链成一个备用链表，Space[0].cur 为头指针，
    //“0”表示空指针
    int i;
    for (i = 0; i < MAXSIZE - 1; ++i)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;
} //Initspace. SL


//在静态单链线性表中査找第 1 个值为 e 的元素
int LocateElem_SL(SLinkList S, ElemType e) {
    //若找到，则返回它在 L 中的位序，否则返回 0
    int i = S[0].cur;                                       // i 指示表中第一个结点
    while (i && S[i].data != e)
        i = S[i].cur;                                       //在表中顺链查找
    return i;
}//LocateElem_SL


//若备用空间链表非空，则 返回 分配的结点下标，否则返回 0
//space[0] 是备用空间链表的头结点，第一个分配的结点为集合 A 的头结点
int Malloc_SL(SLinkList &space) {
    int i = space[0].cur;
    if (space[0].cur)
        space[0].cur = space[i].cur;                        //正好把 i 空出来，i 表示原来 space[0] 的游标 cur
    return i;
}//Mal1oc-SL


//将下标为 k 的空闲结点回收到备用链表
void Free_SL(SLinkList &space, int k) {
    space[k].cur = space[0].cur;                            //空闲结点的 cur 指向 space[0] 的原下一个结点，即 space[0].cur
    space[0].cur = k;                                       //把 k 插入到之前的链表中
}//Free_SL


//依次输入集合 A 和 B 的元素，在一维数组 space 中建立表示集合（A-B) U (B-A)
//的静态链表，S 为其头指针。假设备用空间足够大，space[0].cur 为其头指针。
void difference(SLinkList &space, int &list_s_head_index) {

    InitSpace_SL(space);                                   //初始化备用空间
    list_s_head_index = Malloc_SL(space);                  //生成 S 的头结点，开始时 space[list_s_head_index].data 是空的
    int r_list_s_last_index = list_s_head_index;              // r 指向 S 的当前最后结点
    int list_a_count, list_b_count;
    printf("请输入 A 的元素个数 和 B 的元素个数 (用空格分隔)");
    scanf("%d%d", &list_a_count, &list_b_count);               //输入 A 的元素个数 m 和 B 的元素个数 n

    for (int j = 1; j <= list_a_count; ++j) {                 //建立集合 A 的链表
        int distributed_index = Malloc_SL(space);          //分配结点
        printf("请输入 A 的元素值");
        scanf("%d", &space[distributed_index].data);          //输入 A 的元素值
        space[r_list_s_last_index].cur = distributed_index;
        r_list_s_last_index = distributed_index;              //插人到表尾
    }//for

    space[r_list_s_last_index].cur = 0;                       //尾结点的指针为空

    for (int j = 1; j <= list_b_count; ++j) {                 //依次输入 B 的元素，若不在当前表中，则插入，否则删除

        int b_input_data;
        printf("请输入 B 的元素值");
        scanf("%d", &b_input_data);

        int list_s_head_index_cur_temp = list_s_head_index;
        int list_s_head_index_cur = space[list_s_head_index].cur;                 // k 指向集合 A 中第一个结点

        //遍历 A 集合
        while (list_s_head_index_cur != space[r_list_s_last_index].cur &&
               space[list_s_head_index_cur].data != b_input_data) {         //在当前表中查找
            list_s_head_index_cur_temp = list_s_head_index_cur;                   //list_s_head_index_cur_temp 指向 A 中的最后一个节点的前一个结点
            list_s_head_index_cur = space[list_s_head_index_cur].cur;
        }//while

        if (list_s_head_index_cur ==
            space[r_list_s_last_index].cur) {            //遍历集合 A 的头尾 index 重合，说明当前表中不存在该元素，插入在 r_list_s_last_index 所指结点之后
            int i = Malloc_SL(space);                                          //且 r_list_s_last_index 的位置不变
            space[i].data = b_input_data;
            space[i].cur = space[r_list_s_last_index].cur;
            space[r_list_s_last_index].cur = i;
        } else {                                                                  //该元素已在表中，删除之
            space[list_s_head_index_cur_temp].cur = space[list_s_head_index_cur].cur; //list_s_head_index_cur_temp 正好是 list_s_head_index_cur 的前一个结点，所以 list_s_head_index_cur_temp 的值被覆盖
            Free_SL(space, list_s_head_index_cur);
            if (r_list_s_last_index ==
                list_s_head_index_cur)                     //list_s_head_index_cur 已经被 free 掉了，最后一个结点的 index 是 list_s_head_index_cur_temp
                r_list_s_last_index = list_s_head_index_cur_temp;                 //若删除的是 r 所指结点，则需修改尾指针为 list_s_head_index_cur_temp
        }
    }//for
}//difference

//打印所有备用链表的结点
void Show_EMPTY_SL(SLinkList &space) {
    printf("链表的打印结果是\n");
    int s = Malloc_SL(space); //指向头结点
    while (space[s].cur != 0) {
        std::cout << space[s].data << " ";
        s = Malloc_SL(space);
    }
    std::cout << std::endl;
}

void Show_ALL_SL(SLinkList &space) {
    for (int i = 0; i < MAXSIZE; i++) {
        std::cout << space[i].data << " ";
    }
}